#include <bits/stdc++.h>
using namespace std;

/*
3201. 找出有效子序列的最大长度 I
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个整数数组 nums。

nums 的子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列：

(sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2
返回 nums 的 最长的有效子序列 的长度。

一个 子序列 指的是从原数组中删除一些元素（也可以不删除任何元素），剩余元素保持原来顺序组成的新数组。

 

示例 1：

输入： nums = [1,2,3,4]

输出： 4

解释：

最长的有效子序列是 [1, 2, 3, 4]。

示例 2：

输入： nums = [1,2,1,1,2,1,2]

输出： 6

解释：

最长的有效子序列是 [1, 2, 1, 2, 1, 2]。

示例 3：

输入： nums = [1,3]

输出： 2

解释：

最长的有效子序列是 [1, 3]。

 

提示：

2 <= nums.length <= 2 * 105
1 <= nums[i] <= 107
*/

// 法一
class Solution {
public:
    int maximumLength(vector<int>& nums) {
        int count_odd = 0, count_even = 0;
        for (int x : nums) {
            if (x % 2 == 0) count_even++;
            else count_odd++;
        }
        
        int max_odd = 0;  // 以奇数结尾的最长交替序列长度
        int max_even = 0; // 以偶数结尾的最长交替序列长度
        int max_alt = 0;  // 全局最长交替序列长度
        
        for (int x : nums) {
            if (x % 2 == 0) { // 当前是偶数
                int cur_len = max_odd + 1; // 接在奇数序列后
                max_alt = max(max_alt, cur_len);
                max_even = max(max_even, cur_len);
            } else { // 当前是奇数
                int cur_len = max_even + 1; // 接在偶数序列后
                max_alt = max(max_alt, cur_len);
                max_odd = max(max_odd, cur_len);
            }
        }
        
        return max({count_odd, count_even, max_alt});
    }
};

// 法二
class Solution {
public:
    int maximumLength(vector<int>& nums) {
        // 分别记录 奇数 偶数 相邻元素和为奇数的次数
        int a = nums[0] % 2, b = !a, c = 1;

        // 从第二个元素开始遍历
        for (int i = 1; i < nums.size(); i++) {
            a += nums[i] % 2;       // 累加奇数数量
            b += !(nums[i] % 2);       // 累加偶数数量
            c += (nums[i - 1] + nums[i]) % 2;   // 累加相邻元素为奇数的次数
        }

        return max({a, b, c});
    }
};